package com.yiwenup.leetcode.hot;

/**
 * @PROJECT struct-algorithm
 * @PACKAGE com.yiwenup.leetcode.hot
 * @Author yiwenup
 * @Date 2022-03-14 20:43:24
 * <p>
 * @DESCRIPTION https://leetcode-cn.com/problems/minimum-path-sum/
 */
public class No0064 {

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了95.14%的用户
     * 内存消耗：43.7 MB, 在所有 Java 提交中击败了46.99%的用户
     */
    public int minPathSum(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j == 0) continue;
                else if (i == 0) grid[0][j] += grid[0][j - 1];
                else if (j == 0) grid[i][0] += grid[i - 1][0];
                else grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}
